<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<script>
var ua = navigator.userAgent.toLowerCase();
if(ua.match(/MicroMessenger/i)=="micromessenger") {
    location.href='http://blog.chinaunix.net/article.php?url='+ window.location.href;
}
</script>
        <style>
    .Blog_nav1_2 a em { display:inline-block; width:16px; height:13px; background:url(/image/v.jpg) no-repeat; overflow:hidden;}
</style>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<link rel="stylesheet" type="text/css" href="/css/default/style.css" />
<link rel="stylesheet" type="text/css" href="/css/qqface/qqFace.css" />
<link rel="stylesheet" type="text/css" href="/css/asyncbox/skins/Chrome/asyncbox.css" />
<link rel="stylesheet" type="text/css" href="/assets/6d60aeb8/pager.css" />
<script type="text/javascript" src="/js/jquery.min.js"></script>
<script type="text/javascript" src="/js/jquery.cookies.min.js"></script>
<script type="text/javascript" src="/js/AsyncBox.v1.4.5.js"></script>
<title>外部排序技术之多路归并-g_programming-ChinaUnix博客</title>
<meta name="description" content='

外部排序技术之多路归并
重点：败者树的创建调整函数
1.外部排序概述
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目'/>
<script type='text/javascript' src='http://168.it168.com/a/h600.js'></script>

<script type="text/javascript">
if(/AppleWebKit.*Mobile/i.test(navigator.userAgent) || (/MIDP|SymbianOS|NOKIA|SAMSUNG|LG|NEC|TCL|Alcatel|BIRD|DBTEL|Dopod|PHILIPS|HAIER|LENOVO|MOT-|Nokia|SonyEricsson|SIE-|Amoi|ZTE/.test(navigator.userAgent))){
	try{
		if(!/iPad/i.test(navigator.userAgent)){
			var oldurl=window.location.href;
			var wapUrl= oldurl.replace('blog.chinaunix.net', "m.blog.chinaunix.net") ;
			window.location.href = wapUrl;
		}
	}catch(e){}
}
</script>


<script language="javascript">
//用户是否在线
var isOnLine = '';
$(document).ready(function(){
	var blog = {'name': '', 'name_url': '', 'brief': ''};
	//消息通知显示和隐藏控制
	$('#show_message_slide_button').hover(
		function(){
			$('#message_slide_div').slideDown(100);											   
		},
		function(){
			
		}
	);

	$('#message_slide_div').hover(
		function(){
			
		},
		function(){
			$('#message_slide_div').slideUp(100);
		}
	);
	
	//编辑博客名
	$('#editbna').click(function(){
		blog.name = $('#bnaspan a').text();
		var val = '<input id="bnainput" type="text" style="float:left" value="" rel="' +$(this).attr('rel') + '" /><input id="bnasub" type="button" style="float:left" class="btn1"><input id="bnacanl" type="button" style="float:left" class="btn2"><div class="clear"></div>';
		$('#bnaspan').html(val);
		$('#bnainput').val(blog.name);
		$(this).parent().hide();
	});
	
	$('#bnasub').live('click', function(){
	    var rel = eval('({' + $('#bnainput').attr('rel') + '})');
		var name = $('#bnainput').val();
		if(name != blog.name){
	        $.ajax({
			    type: "POST",
			    url: rel.url,	
			    data: {
				    'name' : name
			    },
			    success:function(data){
				    if(data == 0){
						$('#bnaspan').html(blog.name);
						$('#bnaspan').html('<a href="' + rel.href + '">' + $('#bnaspan').html() + '</a>');
				    }else{
						$('#bnaspan').html(data);
						$('#bnaspan').html('<a href="' + rel.href + '">' + $('#bnaspan').html() + '</a>');
				    }
					$('#editbna').parent().show();
				}
			});
		}else{
		    $('#bnaspan').text(blog.name).html();
			$('#bnaspan').html('<a href="' + rel.href + '">' + $('#bnaspan').html() + '</a>');
			$('#editbna').parent().show();
		}
	});
	
	$('#bnacanl').live('click', function(){
		var rel = eval('({' + $('#bnainput').attr('rel') + '})');
		$('#bnaspan').html('<a href="' + rel.href + '">' + blog.name + '</a>');
		$('#editbna').parent().show();
	});
	
	//编辑签名
	$('#editbrief').click(function(){
	    blog.brief = $('#briefem').text();
		var val = '<input id="brfinput" type="text" style="float:left" value="" rel="' + $(this).attr('rel') + '" /><input id="brfsub" style="float:left"  type="button" class="btn1"><input style="float:left"  id="brfcanl" type="button" class="btn2"><div class="clear"></div>';
		$('#briefem').html(val);
		$('#brfinput').val(blog.brief);
		$(this).parent().hide();
	});
	
	$('#brfsub').live('click', function(){
	    var url = $('#brfinput').attr('rel');
		var brief = $('#brfinput').val();
		if(brief != blog.brief){
	        $.ajax({
			    type: "POST",
			    url: url,	
			    data: {
				    'brief' : brief
			    },
			    success:function(data){
				    if(data == 0){
				        $('#briefem').html(blog.brief);
				    }else{
						$('#briefem').html(data);
				    }
					$('#editbrief').parent().show();
				}
			});
		}else{
		    $('#briefem').text(blog.brief).html();
			$('#editbrief').parent().show();
		}
	});
	
	$('#brfcanl').live('click', function(){
		$('#briefem').html(blog.brief);
		$('#editbrief').parent().show();
	});

});
</script>
</head>
<body>
<div class="box">
  <!-- 一级导航 -->
  <div class="Blog_nav1">
    <div class="Blog_nav1_2"><a href="/"><img src="/image/default/1.png"></a><a href="http://www.chinaunix.net" class="Blog_a1">Chinaunix首页</a>　| 　<a href="http://bbs.chinaunix.net" target="_blank">论坛</a>　| 　<a href="http://u.it168.com/vip/"><font color="red">认证专区</font></a>　| 　<a href="http://blog.chinaunix.net" target="_blank">博客</a><span class="Blog_span1"></span>
            <a href="/site/login.html" class="Blog_a1">登录</a> | <a href="http://u.it168.com/Register?webid=5&returnUrl=http%3A%2F%2Fblog.chinaunix.net%2Fuid-25324849-id-2182916.html" class="Blog_a1">注册</a>
          </div>
	<!--自动提示层-->
	<style>
	.bor13221{border:1px #bbb solid;width:206px;position:absolute;top:34px;left:0;background:#fff; z-index:9999;display:none}
	.bor13221 li{height:26px;line-height:26px;padding-left:6px;color:#555;font-size:14px;cursor:pointer;}
	.here{background:#f3f3f3;}
    </style>

	<!--自动提示层-->
    <div class="Blog_nav1_3" style="position:relative; z-index:9999;">
	 <div class="bor13221">
      <ul>
      </ul>
    </div>
	  <form action='/site/search.html' method='post'>
		<input type="text"  autocomplete="off"  class="Blog_txt1" id='search_input_id' name='keywords'>
		<select class="Bolg_sel1" name='type' id='search_type_blog'>
		  <option value='blog'>博文</option>
		  <option value='author'>博主</option>
		</select>
		<input type="submit" value='' name='submit' class="Blog_btn1">
	 </form>
    </div>
    <div class="clear"></div>
    <div class="Blog_nav1_layer1" id="message_slide_div" style="display:none;">
	    <ul>
	    	<li><a href="/message/private.html">私人消息()</a></li>
	    	<li><a href="/message/system.html">系统消息()</a></li>
	    	<li><a href="/member/request.html">好友请求()</a></li>
	    	<li><a href="/member/notification.html">通知管理()</a></li>
	    </ul>
    </div>
  </div>
   <script type="text/javascript">
  	$(function(){
		//点击添加进文本框
		$(".bor13221 li").live( 'click' , function(e){
			if ( e && e.stopPropagation )
			{
				//因此它支持W3C的stopPropagation()方法
				e.stopPropagation();
			}
			else
			{
				//否则，我们需要使用IE的方式来取消事件冒泡
				window.event.cancelBubble = true; 
			}
			$('#search_input_id').val($(this).text());
			$(".bor13221 ul").html('');
			$(".bor13221").hide();
		});
		$(".bor13221 ul li").live({
			mouseenter:
			function()
			{
				$(".bor13221 ul li").removeClass("here");
				$(this).addClass('here');
			},
			mouseleave:
			function()
			{
				$(".bor13221 ul li").removeClass("here");
				$(this).removeClass('here');
			}
		});
		//自动提示
		$('#search_input_id').keyup(function(event){
			//取消博主的提示
			var search_type_blog = $('#search_type_blog').val();
			if(search_type_blog == 'author') return false;

			var key = $(this).val();
			//获取键值
			var keycode = event.which; //38 上 40 下
			var count = $('.bor13221 ul li').length;
			if(key != '' && keycode != 38 && keycode != 40)
			{
				$.getJSON("http://api.sou.it168.com/autoWenKuCloud?jsoncallback=?",{"ty":"json","offset":"0","limit":"10","q":key}, function(result)
					{
						var arr = result.data;

						var html ='';
						for (i=0;i<arr.length ;i++ )   
						{   
							html += '<li>'+arr[i]+'</li>';
						} 
						
						$('.bor13221 ul').html(html);
						(arr.length > 1) ?  $(".bor13221").show() : $(".bor13221").hide();
					}
				);
			}
			else if(keycode == 38)
			{
				if(count > 0)
				{
					//遍历li
					var curr_li_num;
					$('.bor13221 ul li').each(function(index , dom){
						if($(dom).attr('class') == 'here')
						{
							curr_li_num = index;
							return false;
						}
					}); 
					var next_li_num;
					if(typeof(curr_li_num) == 'undefined')
					{
						next_li_num = count - 1;
					}
					else
					{
						if(curr_li_num == 0)
						{
							next_li_num = count - 1;
						}
						else
						{
							next_li_num = curr_li_num - 1;
						}
					}
					$(".bor13221 ul li").removeClass("here");
					$(".bor13221 ul li:eq(" + next_li_num + ")").addClass("here");
					$('#search_input_id').val($(".bor13221 ul li:eq(" + next_li_num + ")").text());
				}
			}
			else if(keycode == 40)
			{
				if(count > 0)
				{
					//遍历li
					var curr_li_num;
					$('.bor13221 ul li').each(function(index , dom){
						if($(dom).attr('class') == 'here')
						{
							curr_li_num = index;
							return false;
						}
					}); 
					var next_li_num;
					if(typeof(curr_li_num) == 'undefined')
					{
						next_li_num = 0;
					}
					else
					{
						if(curr_li_num == count - 1)
						{
							next_li_num = 0;
						}
						else
						{
							next_li_num = curr_li_num + 1;
						}
					}
					$(".bor13221 ul li").removeClass("here");
					$(".bor13221 ul li:eq(" + next_li_num + ")").addClass("here");
					$('#search_input_id').val($(".bor13221 ul li:eq(" + next_li_num + ")").text());
				}
			}
		});
		$(document).click(function(e){
			$(".bor13221").hide();
		});

	});
  </script>
  <!-- 头 -->
  <!-- 推荐博客-->
  <div class="Blog_header1">
	<div class="img1"></div>    <div class="Blog_header1_1">
      <p class="Blog_p1" ><em><a href="/uid/25324849.html">os.boy</a></em><a href="http://gzprogramming.blog.chinaunix.net">gzprogramming.blog.chinaunix.net</a></p>      <p class="Blog_p2" style="color:#125A94">System Engineer</p>
    </div>
        <div class="Blog_header1_2" id="hide_div1">
    	<span class="Blog_span3"></span>
    	<div class="float_div1" style="white-space:nowrap;" onmouseover="javascript:isMove=false" onmouseout="javascript:isMove=true">
	    <ul id="noticev2">  
		    		    <li><a href="http://blog.chinaunix.net/uid-24789255-id-198226.html" target="_blank">ChinaUnix博客技术文章推荐标准和规范 </a></li>
		    		    <li><a href="http://blog.chinaunix.net/uid-24789255-id-4288187.html" target="_blank">有奖征集：文集--博客系列博文管理</a></li>
		    		    <li><a href="http://blog.chinaunix.net/uid-24789255-id-4289076.html" target="_blank">CU博客频道6月技术图书有奖试读活动 </a></li>
		    	    </ul>
	    </div>
    </div>
            <div class="Blog_header1_3"><a href="/uid/25324849.html">首页</a>　| 　<a href="/uid/25324849/abstract/1.html">博文目录</a>　| 　<a href="/member/profile/uid/25324849.html">关于我</a></div>
  </div>
    
  <!-- 内容部分 -->
  	<script type="text/javascript" src="/highlight/scripts/XRegExp.js"></script> <!-- XRegExp is bundled with the final shCore.js during build -->
<script type="text/javascript" src="/highlight/scripts/shCore.js"></script>
<script type="text/javascript" src="/highlight/scripts/shAutoloader.js"></script>
<link type="text/css" rel="stylesheet" href="/highlight/styles/shCore.css"/>
<link type="text/css" rel="Stylesheet" href="/highlight/styles/shThemeDefault.css" />
<link href="/code/css/fck_editorarea.css" rel="stylesheet" type="text/css" />
<style>
.Blog_p5 em{ display:inline-block; width:16px; height:13px; background:url(/image/v.jpg) no-repeat; overflow:hidden;}
</style>
  <div class="Blog_contain"> 
    <!-- 左 -->
	<style>
    .Blog_left1_1 p a em { display:inline-block; width:16px; height:13px; background:url(/image/v.jpg) no-repeat; overflow:hidden;}
</style>

<script language="javascript">
$(document).ready(function(){
	$('#ConcernBtn').bind('click',function(){
			var cuid = '25324849';
			var url =  '/member/concern.html';
			var type = $(this).attr('rel');
		
			if(type == 'addConcern'){
				$.ajax({
					type : 'get',
					url  : url,
					data : {'op' : 'ajaxadd' , 'cuid' : cuid, 'random' : Math.random()},
					success : function(msg){	
					   if(msg == -1){
						   showErrorMsg('参数错误！');
					   } else if (msg == 0){
						   showErrorMsg('关注失败，没有该用户！');
					   } else if (msg == 1){
						   showErrorMsg('关注失败，您已经关注了该用户！');
					   } else if (msg == 2){
						   $('#ConcernBtn').val('已关注');
						   $('#ConcernBtn').attr('rel','delConcern');
						   showSucceedMsg('关注成功!');
					   } else if (msg == 3){
						   showErrorMsg('未知错误');
					   }
					}
				});	
			} else if ( type == 'delConcern'){
				$.ajax({
					type : 'get',
					url  : url,
					data : {'op' : 'ajaxdel' , 'cuid' : cuid, 'random' : Math.random()},
					success : function(msg){
					   if(msg == 0){
						   showErrorMsg('参数错误！','消息提示');
					   } else if (msg == 1){
						   showErrorMsg('操作失败，请尝试刷新页面重试！','消息提示');
					   } else if (msg == 2){
						   $('#ConcernBtn').val('加关注');
						   $('#ConcernBtn').attr('rel','addConcern');
						   showSucceedMsg('成功取消关注！','消息提示');
					   } else if (msg == 3){
						   showErrorMsg('未知错误！','消息提示'); 
					   }
					}
				});	
			}
	});					   
});

//加好友
function addFriend(fuid, url){
	if(fuid == '' || fuid.length == 0){
		showErrorMsg('缺少参数！','信息提示');
		return false;
	}
	$.ajax({
		   type : 'get',
		   url : url,
		   data : {'op' : 'add', 'fuid' : fuid , 'random' : Math.random()},
		   success : function(msg){
				if(msg == -1){
					showErrorMsg('参数错误！','消息提示');
				} else if (msg == -2){
					showErrorMsg('添加好友失败,没有该用户的信息！','消息提示');
				} else if (msg == -3){
					showErrorMsg('添加好友失败,你不能添加自己为好友！','消息提示');
				} else if (msg == -4){
					showErrorMsg('添加好友未知错误,该错误已被记录！','消息提示');
				} else if (msg == -5){
					showErrorMsg('添加好友失败,你之前已经发送过好友请求,请耐心等待对方同意申请！','消息提示');
				} else if (msg == -6){
					showErrorMsg('添加好友失败,你们已经是好友了！','消息提示');
				} else {
					$.cover(true);
					asyncbox.open({
						id : 'addFriend',
						title : '添加好友',
						url : url,
						data : {'op' : 'add', 'fuid' : fuid , 'random' : Math.random()},
						width : 490,
						height : 180,
						scroll : 'no',
						callback : function(action) {
							if (action == 'close'){
								$.cover(false);
							}	
						}
					});	
				}
		   }
	});	
	
}

//发送短消息
function postMessage(msguid, url){
	if(msguid == '' || msguid.length == 0){
		showErrorMsg('缺少参数！','信息提示');
		return false;
	}
	
	$.ajax({
		   type : 'post',
		   url : url,
		   data : {'op' : 'ajaxpost', 'msguid' : msguid , 'random' : Math.random()},
		   success : function(msg){
				if(msg == -1){
					showErrorMsg('发送失败，缺少收件人对象！','消息提示');
				} else if(msg == -2){
					showErrorMsg('发送失败，自己不能给自己发送短消息！','消息提示');
				} else {
					$.cover(true);
					asyncbox.open({
						id : 'postMessage',
						title : '发送短消息',
						url : url,
						data : {'op' : 'ajaxpost', 'msguid' : msguid , 'random' : Math.random()},
						width : 510,
						height : 255,
						scroll : 'no',
						callback : function(action) {
							if (action == 'close'){
								$.cover(false);
							}	
						}
					});	
				}
		   }
	});	
}

</script>
<div class="Blog_left">
      <div class="Blog_left1 Blog_bg1">
        <div class="Blog_left1_1">
			<!-- 专家博客-->
			<a href="/uid/25324849.html"><img src="http://passport.ixpub.net/data/avatar/025/32/48/49_avatar_middle.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_middle.gif'" /></a>
                        <p><a href="/uid/25324849.html">g_programming</a></p>
                     </div>
        <ul class="Blog_ul1 Blog_noline1">
          <li>博客访问： 597949 </li>
          <li>博文数量： 330 </li>
          <li>博客积分： 7876 </li>
          <!--<li>专家积分： 180</li>-->
          <li>博客等级： 准将 </li>
		  <li>技术积分： 4804 </li>
          <li>用  户  组：  普通用户</li>
          <li>注册时间： 2011-02-23 13:39 </li>
                            </ul>  


        
                <div class="HT_line3 HT_line3_1"></div>
        <ul class="Blog_ul2">
          <li><input type="button" value="加关注" id="ConcernBtn" onclick="showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html')"></li>
          <li><input type="button" value="短消息" id="postMessageBtn" onclick="showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html')"></li>
          <li><input type="button" value="论坛" onclick="location.href='http://bbs.chinaunix.net'"></li>
          <li><input type="button" value="加好友" id="addFriendBtn" onclick="showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html')"></li>
        </ul>
              </div>
        
         
      <div class="Blog_left2 Blog_bg1">
        <div class="Blog_tit1">文章分类</div>
        <div class="Blog_left2_1">
          <p class="Blog_p4"><a href="/uid/25324849/list/1.html">全部博文</a>（330）</p>
          <ul id="blogCla">
                            <li><a href="/uid/25324849/cid-158905-list-1.html" title="/etc目录下文件详解">/etc目录下文件详</a>（1）
                                </li>
                            <li><a href="/uid/25324849/cid-158196-list-1.html" title="PHP相关">PHP相关</a>（1）
                                </li>
                            <li><a href="/uid/25324849/cid-156938-list-1.html" title="Expect">Expect</a>（2）
                                </li>
                            <li><a href="/uid/25324849/cid-156827-list-1.html" title="学习总结">学习总结</a>（4）
                                </li>
                            <li><a href="/uid/25324849/cid-156398-list-1.html" title="守护进程">守护进程</a>（2）
                                </li>
                            <li><span class="Blog_jia1"></span><a href="/uid/25324849/cid-155479-list-1.html" title="Linux图形相关">Linux图形相关</a>（3）
                                    <div style="display:none;" class="zk">
					                        <p><a href="/uid/25324849/sid-155485-list-1.html" title="科学绘图工具">科学绘图工具</a>（1）</p>
                                            <p><a href="/uid/25324849/sid-155481-list-1.html" title="对话框">对话框</a>（2）</p>
                                        </div>
                                </li>
                            <li><a href="/uid/25324849/cid-154717-list-1.html" title="ASCII表">ASCII表</a>（1）
                                </li>
                            <li><a href="/uid/25324849/cid-154701-list-1.html" title="Linux常用命令详解">Linux常用命令详</a>（12）
                                </li>
                            <li><a href="/uid/25324849/cid-154034-list-1.html" title="Ubuntu安装">Ubuntu安装</a>（2）
                                </li>
                            <li><a href="/uid/25324849/cid-153131-list-1.html" title="Linux网络编程相关">Linux网络编程相</a>（4）
                                </li>
                            <li><a href="/uid/25324849/cid-153130-list-1.html" title="多进程和多线程的比较">多进程和多线程的</a>（1）
                                </li>
                            <li><span class="Blog_jia1"></span><a href="/uid/25324849/cid-152786-list-1.html" title="Python相关">Python相关</a>（19）
                                    <div style="display:none;" class="zk">
					                        <p><a href="/uid/25324849/sid-157519-list-1.html" title="Python应用">Python应用</a>（9）</p>
                                            <p><a href="/uid/25324849/sid-157518-list-1.html" title="Python基础">Python基础</a>（10）</p>
                                        </div>
                                </li>
                            <li><a href="/uid/25324849/cid-152776-list-1.html" title="/proc目录下文件详解">/proc目录下文件</a>（5）
                                </li>
                            <li><span class="Blog_jia1"></span><a href="/uid/25324849/cid-151813-list-1.html" title="Shell相关">Shell相关</a>（63）
                                    <div style="display:none;" class="zk">
					                        <p><a href="/uid/25324849/sid-157505-list-1.html" title="Awk应用">Awk应用</a>（4）</p>
                                            <p><a href="/uid/25324849/sid-155484-list-1.html" title="Shell应用">Shell应用</a>（15）</p>
                                            <p><a href="/uid/25324849/sid-152361-list-1.html" title="Shell基础">Shell基础</a>（25）</p>
                                            <p><a href="/uid/25324849/sid-152360-list-1.html" title="Sed相关">Sed相关</a>（7）</p>
                                            <p><a href="/uid/25324849/sid-152359-list-1.html" title="Awk基础">Awk基础</a>（12）</p>
                                        </div>
                                </li>
                            <li><a href="/uid/25324849/cid-101800-list-1.html" title="编写安全的代码">编写安全的代码</a>（5）
                                </li>
                            <li><a href="/uid/25324849/cid-85858-list-1.html" title="各种常用协议">各种常用协议</a>（1）
                                </li>
                            <li><a href="/uid/25324849/cid-73093-list-1.html" title="加密和解密">加密和解密</a>（1）
                                </li>
                            <li><a href="/uid/25324849/cid-19658-list-1.html" title="数据结构">数据结构</a>（13）
                                </li>
                            <li><a href="/uid/25324849/cid-19655-list-1.html" title="心得转载">心得转载</a>（1）
                                </li>
                            <li><span class="Blog_jia1"></span><a href="/uid/25324849/cid-18253-list-1.html" title="《Unix网络编程卷1》">《Unix网络编程卷</a>（16）
                                    <div style="display:none;" class="zk">
					                        <p><a href="/uid/25324849/sid-18254-list-1.html" title="基本函数和结构体">基本函数和结构体</a>（16）</p>
                                        </div>
                                </li>
                            <li><span class="Blog_jia1"></span><a href="/uid/25324849/cid-17723-list-1.html" title="Linux服务器相关">Linux服务器相关</a>（12）
                                    <div style="display:none;" class="zk">
					                        <p><a href="/uid/25324849/sid-158421-list-1.html" title="服务器基础">服务器基础</a>（3）</p>
                                            <p><a href="/uid/25324849/sid-158420-list-1.html" title="NFS服务器">NFS服务器</a>（1）</p>
                                            <p><a href="/uid/25324849/sid-158419-list-1.html" title="TFTP服务器">TFTP服务器</a>（1）</p>
                                            <p><a href="/uid/25324849/sid-158418-list-1.html" title="DHCP服务器">DHCP服务器</a>（1）</p>
                                            <p><a href="/uid/25324849/sid-158417-list-1.html" title="SVN服务器">SVN服务器</a>（1）</p>
                                            <p><a href="/uid/25324849/sid-158416-list-1.html" title="Samba服务器">Samba服务器</a>（1）</p>
                                            <p><a href="/uid/25324849/sid-158415-list-1.html" title="FTP服务器">FTP服务器</a>（2）</p>
                                            <p><a href="/uid/25324849/sid-158414-list-1.html" title="WEB服务器">WEB服务器</a>（2）</p>
                                        </div>
                                </li>
                            <li><a href="/uid/25324849/cid-17665-list-1.html" title="生活点滴">生活点滴</a>（4）
                                </li>
                            <li><a href="/uid/25324849/cid-16928-list-1.html" title="进程相关">进程相关</a>（15）
                                </li>
                            <li><a href="/uid/25324849/cid-16926-list-1.html" title="线程相关">线程相关</a>（7）
                                </li>
                            <li><a href="/uid/25324849/cid-16911-list-1.html" title="常见错误">常见错误</a>（13）
                                </li>
                            <li><a href="/uid/25324849/cid-16638-list-1.html" title="U-BOOT">U-BOOT</a>（2）
                                </li>
                            <li><a href="/uid/25324849/cid-15931-list-1.html" title="Linux内核移植">Linux内核移植</a>（3）
                                </li>
                            <li><a href="/uid/25324849/cid-15733-list-1.html" title="《Linux网络编程》">《Linux网络编程</a>（21）
                                </li>
                            <li><a href="/uid/25324849/cid-15656-list-1.html" title="ARM-linux">ARM-linux</a>（4）
                                </li>
                            <li><a href="/uid/25324849/cid-14928-list-1.html" title="《Linux设备驱动程序">《Linux设备驱动</a>（0）
                                </li>
                            <li><a href="/uid/25324849/cid-14927-list-1.html" title="《Unix环境高级编程》">《Unix环境高级编</a>（0）
                                </li>
                            <li><span class="Blog_jia1"></span><a href="/uid/25324849/cid-14924-list-1.html" title="C程序设计">C程序设计</a>（28）
                                    <div style="display:none;" class="zk">
					                        <p><a href="/uid/25324849/sid-15690-list-1.html" title="Windows">Windows</a>（9）</p>
                                            <p><a href="/uid/25324849/sid-15689-list-1.html" title="Linux">Linux</a>（19）</p>
                                        </div>
                                </li>
                            <li><span class="Blog_jia1"></span><a href="/uid/25324849/cid-14923-list-1.html" title="Linux系统">Linux系统</a>（39）
                                    <div style="display:none;" class="zk">
					                        <p><a href="/uid/25324849/sid-156474-list-1.html" title="邮件相关">邮件相关</a>（1）</p>
                                            <p><a href="/uid/25324849/sid-152959-list-1.html" title="Linux系统时间相关">Linux系统时间相</a>（1）</p>
                                            <p><a href="/uid/25324849/sid-152916-list-1.html" title="Linux系统简介">Linux系统简介</a>（10）</p>
                                            <p><a href="/uid/25324849/sid-152915-list-1.html" title="Linux文件相关">Linux文件相关</a>（9）</p>
                                            <p><a href="/uid/25324849/sid-152914-list-1.html" title="Linux性能管理">Linux性能管理</a>（4）</p>
                                            <p><a href="/uid/25324849/sid-152913-list-1.html" title="Linux程序管理">Linux程序管理</a>（6）</p>
                                            <p><a href="/uid/25324849/sid-152912-list-1.html" title="Linux网络管理">Linux网络管理</a>（8）</p>
                                        </div>
                                </li>
                            <li><a href="/uid/25324849/cid-14922-list-1.html" title="Linux驱动">Linux驱动</a>（22）
                                </li>
                            <li><a href="/uid/25324849/cid-14921-list-1.html" title="ACM初学">ACM初学</a>（1）
                                </li>
                            <li><a href="/uid/25324849/cid--1-list-1.html" title="未分配的博文">未分配的博文</a>（2）
                                </li>
                      </ul>
        </div>
      </div>
      	              <div class="Blog_left2 Blog_bg1">
        <div class="Blog_tit1">文章存档</div>
        <div class="Blog_left2_1" id="blogdtr">
                    <p class="Blog_p4"><span class="Blog_jia1"></span><a href="/uid/25324849/year-2013-list-1.html">2013年</a>（2）</p>
          <ul style="display:none;" class="Blog_ul3 zk">
                        <li><a href="/uid/25324849/year-201307-list-1.html">2013年07月</a>（1）</li>
                        <li><a href="/uid/25324849/year-201302-list-1.html">2013年02月</a>（1）</li>
                      </ul>
                    <p class="Blog_p4"><span class="Blog_jia1"></span><a href="/uid/25324849/year-2012-list-1.html">2012年</a>（160）</p>
          <ul style="display:none;" class="Blog_ul3 zk">
                        <li><a href="/uid/25324849/year-201212-list-1.html">2012年12月</a>（1）</li>
                        <li><a href="/uid/25324849/year-201207-list-1.html">2012年07月</a>（3）</li>
                        <li><a href="/uid/25324849/year-201205-list-1.html">2012年05月</a>（21）</li>
                        <li><a href="/uid/25324849/year-201204-list-1.html">2012年04月</a>（45）</li>
                        <li><a href="/uid/25324849/year-201203-list-1.html">2012年03月</a>（42）</li>
                        <li><a href="/uid/25324849/year-201202-list-1.html">2012年02月</a>（48）</li>
                      </ul>
                    <p class="Blog_p4"><span class="Blog_jia1"></span><a href="/uid/25324849/year-2011-list-1.html">2011年</a>（168）</p>
          <ul style="display:none;" class="Blog_ul3 zk">
                        <li><a href="/uid/25324849/year-201111-list-1.html">2011年11月</a>（2）</li>
                        <li><a href="/uid/25324849/year-201109-list-1.html">2011年09月</a>（5）</li>
                        <li><a href="/uid/25324849/year-201108-list-1.html">2011年08月</a>（18）</li>
                        <li><a href="/uid/25324849/year-201107-list-1.html">2011年07月</a>（1）</li>
                        <li><a href="/uid/25324849/year-201105-list-1.html">2011年05月</a>（3）</li>
                        <li><a href="/uid/25324849/year-201104-list-1.html">2011年04月</a>（102）</li>
                        <li><a href="/uid/25324849/year-201103-list-1.html">2011年03月</a>（37）</li>
                      </ul>
                  </div>
      </div>
      	  	        <div class="Blog_left2 Blog_bg1">
        <div class="Blog_tit1">我的朋友</div>
        <ul class="Blog_ul4">
                    <li><a href="/uid/29631743.html"><img src="http://passport.ixpub.net/data/avatar/029/63/17/43_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/29631743.html" title="镇水铁牛">镇水铁牛</a></p>
          </li>
                    <li><a href="/uid/26756760.html"><img src="http://passport.ixpub.net/data/avatar/026/75/67/60_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/26756760.html" title="xy2bl">xy2bl</a></p>
          </li>
                    <li><a href="/uid/11420219.html"><img src="http://passport.ixpub.net/data/avatar/011/42/02/19_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/11420219.html" title="kouzhaokun">kouzhaok</a></p>
          </li>
                    <li><a href="/uid/29550914.html"><img src="http://passport.ixpub.net/data/avatar/029/55/09/14_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/29550914.html" title="mzh2100">mzh2100</a></p>
          </li>
                    <li><a href="/uid/24774106.html"><img src="http://passport.ixpub.net/data/avatar/024/77/41/06_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/24774106.html" title="Bean_lee">Bean_lee</a></p>
          </li>
                    <li><a href="/uid/28539533.html"><img src="http://passport.ixpub.net/data/avatar/028/53/95/33_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/28539533.html" title="hsg1040175759">hsg10401</a></p>
          </li>
                    <li><a href="/uid/28637059.html"><img src="http://passport.ixpub.net/data/avatar/028/63/70/59_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/28637059.html" title="唐辉19900420">唐辉1990</a></p>
          </li>
                    <li><a href="/uid/18800423.html"><img src="http://passport.ixpub.net/data/avatar/018/80/04/23_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/18800423.html" title="3243166">3243166</a></p>
          </li>
                    <li><a href="/uid/11114210.html"><img src="http://passport.ixpub.net/data/avatar/011/11/42/10_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/11114210.html" title="jiuzhuaxiong">jiuzhuax</a></p>
          </li>
                  </ul>
      </div>
	  	        <div class="Blog_left2 Blog_bg1">
        <div class="Blog_tit1">最近访客</div>
        <ul class="Blog_ul4">
                    <li><a href="/uid/29498003.html"><img src="http://passport.ixpub.net/data/avatar/029/49/80/03_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/29498003.html" title="剑魂箫心">剑魂箫心</a></p>
          </li>
                    <li><a href="/uid/29959938.html"><img src="http://passport.ixpub.net/data/avatar/029/95/99/38_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/29959938.html" title="混水摸人">混水摸人</a></p>
          </li>
                    <li><a href="/uid/30078953.html"><img src="http://passport.ixpub.net/data/avatar/030/07/89/53_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/30078953.html" title="Heday2">Heday2</a></p>
          </li>
                    <li><a href="/uid/30090906.html"><img src="http://passport.ixpub.net/data/avatar/030/09/09/06_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/30090906.html" title="Aray1314">Aray1314</a></p>
          </li>
                    <li><a href="/uid/30099823.html"><img src="http://passport.ixpub.net/data/avatar/030/09/98/23_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/30099823.html" title="dreamyuanjing">dreamyua</a></p>
          </li>
                    <li><a href="/uid/23556733.html"><img src="http://passport.ixpub.net/data/avatar/023/55/67/33_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/23556733.html" title="thunder43x">thunder4</a></p>
          </li>
                    <li><a href="/uid/21261348.html"><img src="http://passport.ixpub.net/data/avatar/021/26/13/48_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/21261348.html" title="csugeo">csugeo</a></p>
          </li>
                    <li><a href="/uid/30093354.html"><img src="http://passport.ixpub.net/data/avatar/030/09/33/54_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/30093354.html" title="firemage">firemage</a></p>
          </li>
                    <li><a href="/uid/28536038.html"><img src="http://passport.ixpub.net/data/avatar/028/53/60/38_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a>
            <p><a href="/uid/28536038.html" title="yg_quantum">yg_quant</a></p>
          </li>
                  </ul>
      </div>
	           <div  class="Blog_left2 Blog_left3 Blog_bg1">
        <div class="Blog_tit1">微信关注</div>
        <div class="">
                <div class="" style="float:left; margin-right:5px;">
                 <img width="90" height="90" alt="" src="/image/IT168.jpg"/>
                 </div><br>
                <div class="" style="margin-top:10px;">
                 <p class="">
                         IT168企业级官微
                </p>
                 <p class="">

                 <br></br>
                 微信号：IT168qiye
                </p>
                </div>
        </div>
<hr size="1" style="clear:both;">
        <div class="" style="clear:both;">
                <div class="" style="float:left; margin-right:5px;">
                 <img width="90" height="90" alt="" src="/image/itpub.jpg"/>
                 </div><br>
                <div class="" style="margin-top:10px;">
                 <p class="">
                         系统架构师大会
                </p>
                 <p class="">

                 <br></br>
                 微信号：SACC2013
                </p>
                </div>
        </div>

</div>
      <div class="Blog_left2 Blog_bg1">
        <div class="Blog_tit1">订阅</div>
        <ul class="Blog_ul5">
          <li><a href="/blog/rss/uid/25324849.html" class="Blog_a4"></a></li>
          <li><a href="http://www.google.com/ig/add?feedurl=http%3A%2F%2Fblog.chinaunix.net%2Fuid%2F25324849.html" class="Blog_a5"></a></li>
        </ul>
      </div>
      <div class="Blog_left2 Blog_left3 Blog_bg1">
        <div class="Blog_tit1">推荐博文</div>
        <ul class="Blog_ul6">
				  			<li>·<a href="/uid-8625039-id-4749801.html" title="redis 集群性能测试结果分析">redis 集群性能测试结果分析...</a></li>
		  			<li>·<a href="/uid-25196040-id-4748915.html" title="weblogic如何只对集群中的一个server调优">weblogic如何只对集群中的一...</a></li>
		  			<li>·<a href="/uid-25799257-id-4752726.html" title="仿迅雷之Android版-简单说下粗糙的适配">仿迅雷之Android版-简单说下...</a></li>
		  			<li>·<a href="/uid-25723371-id-4752702.html" title="OLTP类应用系统之DB2数据库优化最佳实践">OLTP类应用系统之DB2数据库优...</a></li>
		  			<li>·<a href="/uid-20940095-id-4752643.html" title="OpenStack 创建快照(Create Snapshot)过程源码分析">OpenStack 创建快照(Create S...</a></li>
		  						  			<li>·<a href="http://blog.itpub.net/29254281/viewspace-1401413" title="MySQL选用可重复读之前一定要想到的事情(执行计划影响)">MySQL选用可重复读之前一定要...</a></li>
		  			<li>·<a href="http://blog.itpub.net/29371470/viewspace-1401281" title="mysql表分区技术详细介绍">mysql表分区技术详细介绍...</a></li>
		  			<li>·<a href="http://blog.itpub.net/26736162/viewspace-1401193" title="如何创建ASM磁盘">如何创建ASM磁盘</a></li>
		  			<li>·<a href="http://blog.itpub.net/23718752/viewspace-1400738" title="强大的awr format">强大的awr format</a></li>
		  			<li>·<a href="http://blog.itpub.net/26230597/viewspace-1400535" title="Hbase0.98版本的安装部署配置管理（Hadoop2.3、Hbase0.98、Hive0.13整合）">Hbase0.98版本的安装部署配置...</a></li>
		  				
        </ul>
      </div>
      <div class="Blog_left2 Blog_left3 Blog_bg1">
        <div class="Blog_tit1">热词专题</div>
        <ul class="Blog_ul6">
                        <li>·<a href="http://www.dataguru.cn/zhuanti/hadoop220peizhi.shtml" target='blank' title='配置hadoop2.2.0格式化namenode问题'>配置hadoop2.2.0格式化nameno...</a></li>
              <li>·<a href="http://www.dataguru.cn/zhuanti/hadoopshouce.shtml" target='blank' title='hadoop2.2.0安装手册'>hadoop2.2.0安装手册</a></li>
        </ul>
      </div>
	  

	</div>
<script language="javascript">
$(document).ready(function(){
    /*目录树JS效果*/
	$('#blogCla li > span').click(function(){
		var cla = $(this).attr('class');
		if(cla == 'Blog_jia1'){
			//$('#blogCla li > span').removeClass('Blog_jian1').addClass('Blog_jia1');
			//$('#blogCla li > .zk').css('display', 'none');
				
			$(this).removeClass('Blog_jia1').addClass('Blog_jian1');
            $(this).parent().children('.zk').css('display', 'block');
		}else{
			$(this).removeClass('Blog_jian1').addClass('Blog_jia1');
            $(this).parent().children('.zk').css('display', 'none');
		}
	});
		
	$('#blogdtr > p > span').click(function(){
		var cla = $(this).attr('class');
		if(cla == 'Blog_jia1'){
			//$('#blogdtr > .Blog_p4 > span').removeClass('Blog_jian1').addClass('Blog_jia1');
			//$('#blogdtr ul').css('display', 'none');
				
			$(this).removeClass('Blog_jia1').addClass('Blog_jian1');
            $(this).parent().next().css('display', 'block');
		}else{
			$(this).removeClass('Blog_jian1').addClass('Blog_jia1');
            $(this).parent().next().css('display', 'none');
		}
	});
});
</script>    <!-- 右 -->
    <div class="Blog_right1">
      <div class="Blog_right1_1 Blog_right1_11">
        <div class="Blog_right1_2 ">
			<!--推荐博文-->
          <div class="Blog_tit4 Blog_tit5">
                        <b class="Blog_b1"></b>
            <a href="/uid-25324849-id-2182916.html">外部排序技术之多路归并</a>
            <em>2011-08-14 16:18:22</em>
          </div>
          <div class="Blog_con2">
            <div class="Blog_con3">
              <p>分类： <span>C/C++</span></p>
			                </p>
            </div>
           <div class="Blog_wz1" style='word-wrap: break-word;'>
			<DIV>
<DIV class=Section0 style="LAYOUT-GRID:  15.6pt none">
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: center"><SPAN style="FONT-SIZE: 16pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'">外部排序技术</SPAN><SPAN style="FONT-SIZE: 16pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'">之多路归并</SPAN><SPAN style="FONT-SIZE: 16pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 14pt; COLOR: rgb(255,0,0); FONT-FAMILY: '黑体'; mso-spacerun: 'yes'">重点：败者树的创建调整函数</SPAN><SPAN style="FONT-SIZE: 14pt; COLOR: rgb(255,0,0); FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 14pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'">1.外部排序概述</SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 14pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 12pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Arial'; mso-spacerun: 'yes'">外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。</SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 12pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Arial'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 14pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'">2.&nbsp;</SPAN><SPAN style="FONT-SIZE: 14pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'">多路归并的实现</SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 14pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"></SPAN><SPAN style="FONT-SIZE: 14pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_13133099465VX1.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_13133099465VX1.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left">
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"><FONT face=宋体></FONT>2.1&nbsp;胜者树</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名&nbsp;&nbsp;……&nbsp;&nbsp;。</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">示例：我们这里以四路归并为例，假设每个归并段已经在输入缓冲区如下图。</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_13133099582DlD.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_13133099582DlD.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">每路的第一个元素为胜利树的叶子节点，（5,</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">7</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">）比较出5胜出成为其根节点，（29,9）比较9胜出成为其</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">根</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">节点，一次向上生成一棵胜利树，然后我们可以得出5为冠军，将第一路归并段的元素5放入输出缓冲区，然后将第一路第二个元素放到胜利树中如下：</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN>&nbsp;</P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_13133099694ei9.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_13133099694ei9.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">由第一次得到的胜利树知，我们这里只改变了第</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">1路的叶子节点，所有根节点7的右子树不用再比较，（16,7）比较7胜出，然后7和右子树的胜利者比较7胜出得到亚军，只进行了2次比较。</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">所以我们知道：</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;决出第一名需比较：&nbsp;&nbsp;&nbsp;k&nbsp;-&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;次</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;决出第二名需比较：&nbsp;&nbsp;</SPAN><SPAN><IMG height=23 src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-22675.png" width=43></SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;次</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;决出第三名需比较：&nbsp;&nbsp;</SPAN><SPAN><IMG height=23 src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-31472.png" width=43></SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;次&nbsp;.............</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'">2.2&nbsp;败者树</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">与胜利树相类似，败者树是在双亲节点中记录下刚刚进行完的这场比赛的败者，让胜者去参加更高一层的比赛。</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">示例：我们这里以四路归并为例，假设每个归并段已经在输入缓冲区如下图。</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_13133099803hmj.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_13133099803hmj.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">每路的第一个元素为胜利树的叶子节点，（5,</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">7</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">）比较出5胜出</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">7失败</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">成为其根节点，（29,9）比较9胜出</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">29失败</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">成为其</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">根</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">节点</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">，胜者（5,9）进行下次的比赛7失败成为其根节点5胜出输出到输出缓冲区。由第一路归并段输出，所有将第一路归并段的第二个元素加到叶子节点如下图：</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_1313309989uBF9.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_1313309989uBF9.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">加入叶子节点16进行第二次的比较，跟胜利树一样，由于右子树叶子节点没有发生变化其右子树不用再继续比较。</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'">2.3&nbsp;败者树程序实现</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">在创建败者树的时候初始化</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">b[...]和ls[...]，</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">b[0]~b[k-1]为k路的第一个元素，即为败者树的叶子节点，ls[0]~ls[k-1]存储的为每次比赛的失败者。</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/**&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">*&nbsp;已知b[0]到b[k-1]为完全二叉树ls的叶子结点，存有k个关键字，沿从叶子&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">*&nbsp;到根的k条路径将ls调整成为败者树。&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">void&nbsp;CreateLoserTree(LoserTree&nbsp;ls){&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;b[k]&nbsp;=&nbsp;MINKEY;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;设置ls中“败者”的初值&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;for(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;k;&nbsp;++i){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ls[i]&nbsp;=&nbsp;k;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;依次从b[k-1]，b[k-2]，…，b[0]出发调整败者&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;for(i&nbsp;=&nbsp;k&nbsp;-&nbsp;1;&nbsp;i&nbsp;&gt;=&nbsp;0;&nbsp;--i){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Adjust(ls,&nbsp;i);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">}</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_1313310004X4rj.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_1313310004X4rj.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;沿从叶子结点b[s]到根结点ls[0]的路径调整败者树。*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">void&nbsp;Adjust(LoserTree&nbsp;ls,&nbsp;int&nbsp;s){&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i,&nbsp;t;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;ls[t]是b[s]的双亲结点&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;t&nbsp;=&nbsp;(s&nbsp;+&nbsp;k)&nbsp;/&nbsp;2;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;while(t&nbsp;&gt;&nbsp;0){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;s指示新的胜者&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(b[s]&nbsp;&gt;&nbsp;b[ls[t]]){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp;s;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s&nbsp;=&nbsp;ls[t];&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ls[t]&nbsp;=&nbsp;i;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t&nbsp;=&nbsp;t&nbsp;/&nbsp;2;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;ls[0]&nbsp;=&nbsp;s;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">}</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">第一次调整：</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: center"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_1313310014gZY6.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_1313310014gZY6.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">由程序可以，先找到叶子节点的父节点，</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">t&nbsp;=&nbsp;(s&nbsp;+&nbsp;k)&nbsp;/&nbsp;2</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;=&nbsp;3&nbsp;</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">（</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">s为3），</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;while(t&nbsp;&gt;&nbsp;0){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;s指示新的胜者&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(b[s]&nbsp;&gt;&nbsp;b[ls[t]]){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp;s;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s&nbsp;=&nbsp;ls[t];&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ls[t]&nbsp;=&nbsp;i;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t&nbsp;=&nbsp;t&nbsp;/&nbsp;2;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">b[ls[t=3]]&nbsp;=&nbsp;b[k]&nbsp;=&nbsp;MINKEY&nbsp;&lt;&nbsp;b[s]&nbsp;=&nbsp;b[3]&nbsp;则交换ls[t]=k和s=3，然后t除以2，t/2&nbsp;=&nbsp;1，&nbsp;b[ls[1]]&nbsp;=&nbsp;b[k]&nbsp;=&nbsp;MINKEY&nbsp;,b[s=k]=MINKEY,直到跳出循环，然后</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;ls[0]&nbsp;=&nbsp;s;&nbsp;</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">由于</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">ls[0]&nbsp;=&nbsp;s&nbsp;=&nbsp;k，所有不变；</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: center"><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_1313310026ZSn5.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_1313310026ZSn5.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">由第二路归并树</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">程序进入调整函数，找到父节点为</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">3，然后就是b[2]和b[3]比较，b[3]&nbsp;=&nbsp;9胜出，则留在ls[3]&nbsp;=&nbsp;2，进入下一层的为ls[1]&nbsp;=&nbsp;3；</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: center"><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_13133100448KUU.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_13133100448KUU.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">由第一路归并树进入调整函数，找到父节点为</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">2，然后是b[1]和b[k=4]比较由于b[4]为最小值，所有b[4]胜出，b[1]失败留在父节点ls[2]&nbsp;=&nbsp;1，胜者进入上一层与ls[1]比较，很明显b[4]为最小值胜出到达ls[0]，留在ls[1]&nbsp;=&nbsp;3；</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: center"><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"><a href="http://blog.chinaunix.net/attachment/201108/14/25324849_1313310053Z86x.jpg" target="_blank"><IMG src="http://blog.chinaunix.net/attachment/201108/14/25324849_1313310053Z86x.jpg" .load="imgResize(this, 650);" border=0 ;></A></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">由第一路归并树进入调整树，先找到父节点<FONT face="Times New Roman">2</FONT><FONT face=宋体>，然后与父节点比较</FONT><FONT face="Times New Roman">b[0]</FONT><FONT face=宋体>胜出，</FONT><FONT face="Times New Roman">b[1]</FONT><FONT face=宋体>依旧留在</FONT><FONT face="Times New Roman">ls[2]</FONT><FONT face=宋体>，继续上一层的比较直到为上图为止。</FONT></SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">我们通过对创建败者树的分析可以知道，程序利用初始化败者树全为第<FONT face="Times New Roman">k</FONT><FONT face=宋体>路，一个不存在的一路归并树，并且置第</FONT><FONT face="Times New Roman">k</FONT><FONT face=宋体>路的值</FONT><FONT face="Times New Roman">b[k]</FONT><FONT face=宋体>为最小值，这是为了让它在每次比较中都能胜出，让第一次比较的值留在失败者的位置，第二次比较的时候自然就跟下一路比较了，这样设计可以减少程序设计的特殊性，避免了特殊情况的出现。创建好败者树后，就可以利用败者树的性质来进行判断了。</FONT></SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(0,0,255); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">实现代码：</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(255,0,0); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">（为了防止归并段变为空的情况，我们将每路归并段最后都加入</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(255,0,0); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"> </SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(255,0,0); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(255,0,0); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(255,0,0); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(255,0,0); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(255,0,0); FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">了一个最大元素）</SPAN><SPAN style="FONT-SIZE: 12pt; COLOR: rgb(255,0,0); FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#include&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&lt;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">stdio.h</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&gt;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#include&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&lt;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">stdlib.h</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&gt;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#include&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&lt;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">string.h</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&gt;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;TRUE&nbsp;1&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;FALSE&nbsp;0&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;OK&nbsp;1&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;ERROR&nbsp;0&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;INFEASIBLE&nbsp;-1&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;MINKEY&nbsp;-1&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;MAXKEY&nbsp;100&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;Status是函数的类型,其值是函数结果状态代码，如OK等&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">typedef&nbsp;int&nbsp;Status;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;Boolean是布尔类型,其值是TRUE或FALSE&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">typedef&nbsp;int&nbsp;Boolean;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;一个用作示例的小顺序表的最大长度&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;MAXSIZE&nbsp;20&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">typedef&nbsp;int&nbsp;KeyType;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;k路归并&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;k&nbsp;3&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;设输出M个数据换行&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">#define&nbsp;M&nbsp;10&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;k+1个文件指针(fp[k]为大文件指针)，全局变量&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">FILE&nbsp;*fp[k&nbsp;+&nbsp;1];&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;败者树是完全二叉树且不含叶子，可采用顺序存储结构&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">typedef&nbsp;int&nbsp;LoserTree[k];&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">typedef&nbsp;KeyType&nbsp;ExNode,&nbsp;External[k+1];&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;全局变量&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">External&nbsp;b;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;从第i个文件(第i个归并段)读入该段当前第1个记录的关键字到外结点&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">int&nbsp;input(int&nbsp;i,&nbsp;KeyType&nbsp;*a){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;j&nbsp;=&nbsp;fscanf(fp[i],&nbsp;"%d&nbsp;",&nbsp;a);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;if(j&nbsp;&gt;&nbsp;0){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("%d\n",&nbsp;*a);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;1;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}else{&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;将第i个文件(第i个归并段)中当前的记录写至输出归并段&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">void&nbsp;output(int&nbsp;i){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;fprintf(fp[k],&nbsp;"%d&nbsp;",&nbsp;b[i]);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/*&nbsp;沿从叶子结点b[s]到根结点ls[0]的路径调整败者树。*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">void&nbsp;Adjust(LoserTree&nbsp;ls,&nbsp;int&nbsp;s){&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i,&nbsp;t;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;ls[t]是b[s]的双亲结点&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;t&nbsp;=&nbsp;(s&nbsp;+&nbsp;k)&nbsp;/&nbsp;2;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;while(t&nbsp;&gt;&nbsp;0){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;s指示新的胜者&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(b[s]&nbsp;&gt;&nbsp;b[ls[t]]){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp;s;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s&nbsp;=&nbsp;ls[t];&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ls[t]&nbsp;=&nbsp;i;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t&nbsp;=&nbsp;t&nbsp;/&nbsp;2;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;ls[0]&nbsp;=&nbsp;s;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/**&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">*&nbsp;已知b[0]到b[k-1]为完全二叉树ls的叶子结点，存有k个关键字，沿从叶子&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">*&nbsp;到根的k条路径将ls调整成为败者树。&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">void&nbsp;CreateLoserTree(LoserTree&nbsp;ls){&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;b[k]&nbsp;=&nbsp;MINKEY;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;设置ls中“败者”的初值&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;for(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;k;&nbsp;++i){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ls[i]&nbsp;=&nbsp;k;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;依次从b[k-1]，b[k-2]，…，b[0]出发调整败者&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;for(i&nbsp;=&nbsp;k&nbsp;-&nbsp;1;&nbsp;i&nbsp;&gt;=&nbsp;0;&nbsp;--i){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Adjust(ls,&nbsp;i);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">/**&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">*&nbsp;利用败者树ls将编号从0到k-1的k个输入归并段中的记录归并到输出归并段。&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">*&nbsp;b[0]至b[k-1]为败者树上的k个叶子结点，分别存放k个输入归并段中当前记录的关键字。&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">void&nbsp;K_Merge(LoserTree&nbsp;ls,&nbsp;External&nbsp;b){&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i,&nbsp;q;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;分别从k个输入归并段读人该段当前第一个记录的关键字到外结点&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;for(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;k;&nbsp;++i)&nbsp;{&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;input(i,&nbsp;&amp;b[i]);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;建败者树ls，选得最小关键字为b[ls[0]].key&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;CreateLoserTree(ls);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;while(b[ls[0]]&nbsp;!=&nbsp;MAXKEY){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;q指示当前最小关键字所在归并段&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q&nbsp;=&nbsp;ls[0];&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;将编号为q的归并段中当前（关键字为b[q].key）的记录写至输出归并段&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output(q);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;从编号为q的输入归并段中读人下一个记录的关键字&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(input(q,&nbsp;&amp;b[q])&nbsp;&gt;&nbsp;0){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;调整败者树，选择新的最小关键字&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Adjust(ls,q);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;将含最大关键字MAXKEY的记录写至输出归并段&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;output(ls[0]);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">void&nbsp;show(KeyType&nbsp;t)&nbsp;{&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;printf("(%d)",&nbsp;t);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">int&nbsp;main(){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;KeyType&nbsp;r;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i,&nbsp;j;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;fname[k][4],&nbsp;fout[5]&nbsp;=&nbsp;"out",&nbsp;s[3];&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;LoserTree&nbsp;ls;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;依次打开f0,f1,f2,…,k个文件&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;for(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;k;&nbsp;i++){&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;生成k个文件名f0,f1,f2,…&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;itoa(i,&nbsp;s,&nbsp;10);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;strcpy(fname[i],&nbsp;"f");&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;strcat(fname[i],&nbsp;s);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;以读的方式打开文件f0,f1,…&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fp[i]&nbsp;=&nbsp;fopen(fname[i],&nbsp;"r");&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("有序子文件f%d的记录为:\n",i);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;依次将f0,f1,…的数据读入r&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do{&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j&nbsp;=&nbsp;fscanf(fp[i],&nbsp;"%d&nbsp;",&nbsp;&amp;r);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;输出r的内容&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(j&nbsp;==&nbsp;1){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;show(r);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}while(j&nbsp;==&nbsp;1);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("\n");&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;使fp[i]的指针重新返回f0,f1,…的起始位置，以便重新读入内存&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rewind(fp[i]);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;以写的方式打开大文件fout&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;fp[k]&nbsp;=&nbsp;fopen(fout,&nbsp;"w");&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;利用败者树ls将k个输入归并段中的记录归并到输出归并段，即大文件fout&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;K_Merge(ls,&nbsp;b);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;关闭文件f0,f1,…和文件fout&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;for(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;=&nbsp;k;&nbsp;i++){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fclose(fp[i]);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;以读的方式重新打开大文件fout验证排序&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;fp[k]&nbsp;=&nbsp;fopen(fout,&nbsp;"r");&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;printf("排序后的大文件的记录为:\n");&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp;1;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;do{&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;将fout的数据读入r&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j&nbsp;=&nbsp;fscanf(fp[k],&nbsp;"%d&nbsp;",&nbsp;&amp;r);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;输出r的内容&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(j&nbsp;==&nbsp;1){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;show(r);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;换行&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(i++&nbsp;%&nbsp;M&nbsp;==&nbsp;0){&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("\n");&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;}while(j&nbsp;==&nbsp;1);&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;printf("\n");&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;关闭大文件fout&nbsp;*/&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;fclose(fp[k]);&nbsp;&nbsp;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;</SPAN><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-INDENT: 21pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">}</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Verdana'; mso-spacerun: 'yes'">测试数据</SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">:</SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(255,0,0); FONT-STYLE: normal; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">注意在每个文件后面都应该加一个哨兵，即一个最大值</SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(255,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Verdana'; mso-spacerun: 'yes'"><BR></SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Verdana'; mso-spacerun: 'yes'">f0:&nbsp;10&nbsp;15&nbsp;16&nbsp;100&nbsp;</SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Verdana'; mso-spacerun: 'yes'"><BR></SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Verdana'; mso-spacerun: 'yes'">f1:&nbsp;9&nbsp;18&nbsp;20&nbsp;100</SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Verdana'; mso-spacerun: 'yes'"><BR></SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Verdana'; mso-spacerun: 'yes'">f2:&nbsp;20&nbsp;22&nbsp;40&nbsp;100</SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Verdana'; mso-spacerun: 'yes'"><BR></SPAN><SPAN style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; COLOR: rgb(0,0,0); FONT-STYLE: normal; FONT-FAMILY: 'Verdana'; mso-spacerun: 'yes'">out:&nbsp;9&nbsp;10&nbsp;15&nbsp;16&nbsp;18&nbsp;20&nbsp;20&nbsp;22&nbsp;40&nbsp;100</SPAN><SPAN style="FONT-SIZE: 10.5pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'">&nbsp;</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: 'Times New Roman'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'">参考文献：</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '黑体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">[1]&nbsp;</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">http://baike.baidu.com/view/1368718.htm</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P>
<P class=p0 style="MARGIN-TOP: 0pt; MARGIN-BOTTOM: 0pt; TEXT-ALIGN: left"><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'">[2]&nbsp;http://blog.csdn.net/nomad2/archive/2007/12/15/1940266.aspx</SPAN><SPAN style="FONT-SIZE: 12pt; FONT-FAMILY: '宋体'; mso-spacerun: 'yes'"></SPAN></P></DIV></DIV>           </div>
            <!-- <div class="Blog_con3_1">管理员在2009年8月13日编辑了该文章文章。</div> -->
            <div class="Blog_con2_1 Blog_con3_2">
              <div>
			  <!--<img src="/image/default/tu_8.png">-->
			  <!-- JiaThis Button BEGIN -->
				<div class="bdsharebuttonbox"><A class=bds_more href="#" data-cmd="more"></A><A class=bds_qzone title=分享到QQ空间 href="#" data-cmd="qzone"></A><A class=bds_tsina title=分享到新浪微博 href="#" data-cmd="tsina"></A><A class=bds_tqq title=分享到腾讯微博 href="#" data-cmd="tqq"></A><A class=bds_renren title=分享到人人网 href="#" data-cmd="renren"></A><A class=bds_weixin title=分享到微信 href="#" data-cmd="weixin"></A></div>
<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];</script>
				<!-- JiaThis Button END -->
			  </div>
              阅读(8643) | 评论(1) | 转发(4) |
			                <div class="HT_line3"></div>
            </div>
            <div class="Blog_con3_3">
              <div><span id='digg_num'>0</span><a href="javascript:void(0)" id='digg' bid='2182916' url='/blog/digg.html' ></a></div>
              <p>上一篇：<a href="/uid-25324849-id-2182899.html">内部排序技术</a></p>
              <p>下一篇：<a href="/uid-25324849-id-2182917.html">排序之qsort函数</a></p>
            </div>
          </div>
          <div class="Blog_con3_4">
            <div class="Blog_tit2 Blog_tit6">相关热门文章</div>
			            <ul class="Blog_ul7">
						  <li><span class="Blog_span6"></span><a href="http://blog.chinaunix.net/uid-30068132-id-4710928.html" title='为企业发展营造良好的外部环境' target='blank' >为企业发展营造良好的外部环境...</a></li>
						  <li><span class="Blog_span6"></span><a href="http://blog.chinaunix.net/uid-30007806-id-4710842.html" title='基于DSP的恒流充电电源设计方案' target='blank' >基于DSP的恒流充电电源设计方...</a></li>
						  <li><span class="Blog_span6"></span><a href="http://blog.chinaunix.net/uid-30007806-id-4710837.html" title='宽动态监控摄像机CCD/CMOS-DSP解析' target='blank' >宽动态监控摄像机CCD/CMOS-DSP...</a></li>
						  <li><span class="Blog_span6"></span><a href="http://blog.chinaunix.net/uid-30023913-id-4710740.html" title='房产业兴衰走向将趋于理性' target='blank' >房产业兴衰走向将趋于理性...</a></li>
						  <li><span class="Blog_span6"></span><a href="http://blog.chinaunix.net/uid-30066355-id-4710668.html" title='头发种植要多少钱?' target='blank' >头发种植要多少钱?</a></li>
			            </ul>
			            <ul class="Blog_ul7">
						  <li><span class="Blog_span7"></span><a href="/uid-26615473-id-3056538.html" title='test123' target='blank' >test123</a></li>
						  <li><span class="Blog_span7"></span><a href="/uid-23629988-id-3018793.html" title='编写安全代码——小心有符号数的右移操作' target='blank' >编写安全代码——小心有符号数...</a></li>
						  <li><span class="Blog_span7"></span><a href="/uid-233938-id-162619.html" title='使用openssl api进行加密解密' target='blank' >使用openssl api进行加密解密...</a></li>
						  <li><span class="Blog_span7"></span><a href="/uid-233938-id-162628.html" title='一段自己打印自己的c程序' target='blank' >一段自己打印自己的c程序...</a></li>
						  <li><span class="Blog_span7"></span><a href="/uid-233938-id-162563.html" title='sql relay的c++接口' target='blank' >sql relay的c++接口</a></li>
			            </ul>
            <ul class="Blog_ul7">
						  <li><span class="Blog_span6"></span><a href="http://ask.chinaunix.net/question/785702" title='谁能够帮我解决LINUX  2.6  10版本驱动' target='blank'  >谁能够帮我解决LINUX  2.6  10...</a></li>
						  <li><span class="Blog_span6"></span><a href="http://ask.chinaunix.net/question/785701" title='现在的博客积分不会更新了吗？' target='blank'  >现在的博客积分不会更新了吗？...</a></li>
						  <li><span class="Blog_span6"></span><a href="http://ask.chinaunix.net/question/785686" title='shell怎么读取网页内容' target='blank'  >shell怎么读取网页内容...</a></li>
						  <li><span class="Blog_span6"></span><a href="http://ask.chinaunix.net/question/785684" title='ssh等待连接的超时问题' target='blank'  >ssh等待连接的超时问题...</a></li>
						  <li><span class="Blog_span6"></span><a href="http://ask.chinaunix.net/question/785661" title='curl: (56) Recv failure: Connection reset by peer' target='blank'  >curl: (56) Recv failure: Con...</a></li>
			            </ul>
            <div class="clear"></div>
          </div>
		  <!--
          <div class="Blog_con3_4 Blog_con3_5">
            <div class="Blog_tit2 Blog_tit7">热门推荐</div>
            <ul>
			              <li><a href="" title="" target='blank' ></a></li>
			            </ul>
          </div>
		  -->
        </div>
      </div>
      <div class="Blog_right1_7" id='replyList'>
		<div class="Blog_tit3">给主人留下些什么吧！~~</div>
														<!--不包含引用-->
					<div class="Blog_right1_8">
					  <div class="Blog_right_img1"><a href='/uid/28732386.html' ><img src="http://passport.ixpub.net/data/avatar/028/73/23/86_avatar_small.jpg" onerror="this.onerror=null;this.src='http://passport.ixpub.net/images/noavatar_small.gif'" /></a></div>
					  <div class="Blog_right_font1">
                                              						<p class="Blog_p5"><span><a href='/uid/28732386.html' ><span>rrammstein</span></a></span>2013-03-18 18:01:06</p>
                                              						<p class="Blog_p6">学习了！<img src="/image/qqface/65.gif" /></p>                                     
						<div class="div1"><a href="javascript:void(0);" class="Blog_a10"  toid='28732386' bid='2182916' cid='587279' tname='rrammstein'>回复</a> | <a href="javascript:;" onclick="showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');" class='box_report'>举报</a></div>
						<!-- 评论占位框-->
						<div class='z_move_comment' style='display:none'>
						</div>
					  </div>
					  <div class="Blog_line1"></div>
					</div>
											<!-- 评论分页-->
		<div class="Blog_right1_6 Blog_right1_12">
        		</div>
		<!-- 评论分页-->
        <div class="Blog_right1_10">
          <div class="Blog_tit3">评论热议</div>
		  		 <!--未登录 -->
        <div class="Blog_right1_8">
          <div class="nologin_con1"> 请登录后评论。
            <p><a href="/site/login.html">登录</a> <a href="http://sso.chinaunix.net/Register?return_url=http%3A%2F%2Ft.cublog.com%2F">注册</a></p>
          </div>
        </div>
        <br>
        <div>
            <div style="float:left;margin-left:70px;margin-right:10px;">
             <script type="text/javascript">
            var cpro_id = "u1625692";
            </script>
            <script src="http://cpro.baidustatic.com/cpro/ui/c.js" type="text/javascript"></script>
            </div>
            <div style="margin-left:10px;">
            <script type="text/javascript">
            var cpro_id = "u1625694";
            </script>
            <script src="http://cpro.baidustatic.com/cpro/ui/c.js" type="text/javascript"></script>
            </div>
        </div>
		
        </div>
      </div>
    </div>
  </div>
  <input type='hidden' id='report_url' value='/blog/ViewReport.html' />

<script type="text/javascript">
  	//测试字符串的长度 一个汉字算2个字节
	function mb_strlen(str)
	{
		var len=str.length;
		var totalCount=0;
		for(var i=0;i<len;i++)
		{
			var c = str.charCodeAt(i);
			if ((c >= 0x0001 && c <= 0x007e) || (0xff60<=c && c<=0xff9f)) {
				totalCount++;
			}else{
				totalCount+=2;
			}
		}
		return totalCount;
	}
	/*
	var Util = {};
	Util.calWbText = function (text, max){
		if(max === undefined)
			max = 500;
		var cLen=0;
		var matcher = text.match(/[^\x00-\xff]/g),
			wlen  = (matcher && matcher.length) || 0;
		//匹配url链接正则 http://***
		var pattern = /http:\/\/([\w-]+\.)+[\w-]+(\/*[\w-\.\/\?%&=][^\s^\u4e00-\u9fa5]*)?/gi;
		//匹配的数据存入数组
		var arrPt = new Array();
		var i = 0;
		while((result = pattern.exec(text)) != null){
			arrPt[i] = result[0];
			i++;
		}
		//替换掉原文本中的链接
		for(var j = 0;j<arrPt.length;j++){
			text = text.replace(arrPt[j],"");
		}
		//减掉链接所占的长度
		return Math.floor((max*2 - text.length - wlen)/2 - 12*i);
	};
	*/
	var allowComment = '0';
	
	//举报弹出层
	function showJuBao(url, cid){
		
			$.cover(false);
			asyncbox.open({
				id  : 'report_thickbox',
				url : url,
				title : '举报违规',
				width : 378,
				height : 240,
				scroll : 'no',
				data : {
					'cid'	 : cid,
					'idtype' : 2 
				},
				callback : function(action){
					if(action == 'close'){
						$.cover(false);
					}
				}
			});
	}

	$(function(){

		//创建管理员删除的弹出层
		$('#admin_article_del').click(function(){
			$.cover(false);
			asyncbox.open({
				id : 'class_thickbox',
				html : '<div class="HT_layer3_1"><ul><li class="HT_li1">操作原因：<select class="HT_sel7" id="del_type" name="del_type"><option value="广告文章">广告文章</option><option value="违规内容">违规内容</option><option value="标题不明">标题不明</option><option value="文不对题">文不对题</option></select></li><li class="HT_li1" ><input class="HT_btn4" id="admin_delete"  type="button" /></li></ul></div>',
				title : '选择类型',
				width : 300,
				height : 150,
				scroll : 'no',
				callback : function(action){
					if(action == 'close'){
						$.cover(false);
					}
				}
			});
		});
		$('#admin_delete').live('click' , function(){
			///blog/logicdel/id/3480184/url/%252Fblog%252Findex.html.html
			var type = $('#del_type').val();
			var url = '/blog/logicdel/id/2182916/url/%252Fuid%252F25324849.html.html';
			window.location.href= url + '?type=' + type;
		});


		//顶  js中暂未添加&过滤 
		$('#digg').live('click' , function(){

			if(isOnLine == '' )
			{
				//showErrorMsg('登录之后才能进行此操作' , '消息提示');
				showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');
				return false;
			}

			var bid = $('#digg').attr('bid');
			var url = $('#digg').attr('url');

			var digg_str = $.cookie('digg_id');
			if(digg_str != null)
			{
				var arr= new Array(); //定义一数组

				arr = digg_str.split(","); //字符分割     
				for( i=0 ; i < arr.length ; i++ )   
				{   
					if(bid == arr[i])
					{
						showErrorMsg('已经赞过该文章', '消息提示'); 
						return false;
					}
				} 
			}
			$.ajax({
				type:"POST",
				url:url,	
				data: {
					'bid' : bid 
				},
				dataType: 'json',
				success:function(msg){
					if(msg.error == 0)
					{
						var num = parseInt($('#digg_num').html(),10);
						num += 1;
						$('#digg_num').html(num);
						$('#digg').die();

						if(digg_str == null)
						{
							$.cookie('digg_id', bid, {expires: 30 , path: '/'});
						}
						else
						{
							$.cookie('digg_id', digg_str + ',' + bid, {expires: 30 , path: '/'});
						}
						showSucceedMsg('谢谢' , '消息提示');
					}
					else if(msg.error == 1)
					{
						//showErrorMsg(msg.error_content , '消息提示'); 
						showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');
					}
					else if(msg.error == 2)
					{
						showErrorMsg(msg.error_content , '消息提示'); 
					}
				}
			});
		});
		//举报弹出层
		/*$('.box_report').live('click' , function(){
			if(isOnLine == '' )
			{
				//showErrorMsg('登录之后才能进行此操作' , '消息提示');
				showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');
				return false;
			}
			var url = $('#report_url').val();
			var cid = $(this).attr('cid');
			$.cover(false);
			asyncbox.open({
				id  : 'report_thickbox',
				url : url,
				title : '举报违规',
				width : 378,
				height : 240,
				scroll : 'no',
				data : {
					'cid'	 : cid,
					'idtype' : 2 
				},
				callback : function(action){
					if(action == 'close'){
						$.cover(false);
					}
				}
			});
		});*/


		//评论相关代码
		
		//点击回复显示评论框
		$('.Blog_a10').live('click' , function(){
			if(isOnLine == '' )
			{
				//showErrorMsg('登录之后才能进行此操作' , '消息提示');
				showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');
				return false;
			}

			if(allowComment == 1)
			{
				showErrorMsg('该博文不允许评论' , '消息提示'); 
				return false;
			}
			var tid = $(this).attr('toid');//留言作者id
			var bid = $(this).attr('bid');//blogid
			var cid = $(this).attr('cid');//留言id
			var tname = $(this).attr('tname');
			var tpl  = '<div class="Blog_right1_9">';
				tpl +=	 '<div class="div2">';
				tpl +=     '<textarea name="" cols="" rows="" class="Blog_ar1_1" id="rmsg">文明上网，理性发言...</textarea>';
				tpl +=	 '</div>';
				tpl +=   '<div class="div3">';
				tpl +=		'<div class="div3_2"><a href="javascript:void(0);" class="Blog_a11" id="quota_sbumit" url="/Comment/PostComment.html" tid="'+tid+'" bid="'+bid+'" cid="'+cid+'" tname="'+tname+'" ></a><a href="javascript:void(0)" id="qx_comment" class="Blog_a12"></a></div>';
				tpl +=		'<div class="div3_1"><a href="javascript:void(0);" id="mface"><span></span>表情</a></div>';
				tpl +=		'<div class="clear"></div>';
				tpl +=	 '</div>';
				tpl +=  '</div>';
			$('.z_move_comment').html('');
			$(this).parents('.Blog_right1_8').find('.z_move_comment').html(tpl).show();
		});
		//引用的评论提交
		$('#quota_sbumit').live('click' , function(){

			if(isOnLine == '' )
			{
				//showErrorMsg('登录之后才能进行此操作' , '消息提示');
				showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');
				return false;
			}

			var bid   = $(this).attr('bid');
			var tid   = $(this).attr('tid');//被引用人的id
			var qid   = $(this).attr('cid');//引用的id
			var url = $(this).attr('url');
			var text = $('#rmsg').val();
			var tname = $(this).attr('tname');
			if(text == '' || text=='文明上网，理性发言...')
			{
				showErrorMsg('评论内容不能为空！' , '消息提示'); 
				return false;
			}
			else
			{
				if(mb_strlen(text) > 1000){
					showErrorMsg('评论内容不能超过500个汉字' , '消息提示'); 
					return false;
				}
			}
		    $.ajax({
		        type: "post",
			    url: url ,
			    data: {'bid': bid , 'to' : tid , 'qid' : qid , 'text': text , 'tname' : tname },
				dataType: 'json',
			    success: function(data){
				    if(data.code == 1){
						var tpl =  '<div class="Blog_right1_8">';
							tpl+=     '<div class="Blog_right_img1"><a href="' +data.info.url+ '" >' + data.info.header + '</a></div>';
							tpl+=     '<div class="Blog_right_font1">';
							tpl+=         '<p class="Blog_p5"><span><a href="' +data.info.url+ '" >' + data.info.username + '</a></span>' + data.info.dateline + '</p>';
							tpl+=         '<p class="Blog_p7"><a href="' + data.info.quota.url + '">' + data.info.quota.username + '</a>：'+ data.info.quota.content + '</p>';
							tpl+=         '<p class="Blog_p8">' + data.info.content + '</p><span class="span_text1"><a href="javascript:void(0);" class="Blog_a10" toid=' + data.info.fuid + ' bid=' + data.info.bid + ' cid=' + data.info.cid + '  tname = ' + data.info.username + ' >回复</a> | 　<a class="comment_del_mark" style="cursor:pointer" url="' + data.info.delurl + '" >删除</a>　| 　<a href="javascript:showJuBao(\'/blog/ViewReport.html\','+data.info.cid+')" class="box_report" cid="' + data.info.cid + '" >举报</a></span></div>';
							tpl+=         '<div class="z_move_comment" style="display:none"></div>';
							tpl+=	      '<div class="Blog_line1"></div></div>';
							$('#replyList .Blog_right1_8:first').before(tpl);
							$('.z_move_comment').html('').hide();
				    }
					else if(data.code == -1){
						//showErrorMsg(data.info , '消息提示'); 
						showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');
			        }
                },
			    error: function(){//请求出错处理
                        
                }
			});
		});
		//底部发表评论
		$('#submitmsg').click(function(){
			if(allowComment == 1)
			{
				showErrorMsg('该博文不允许评论' , '消息提示'); 
				return false;
			}
			var bid   = $(this).attr('bid');
			var toid  = $(this).attr('toid');
			var text = $('#reply').val();
			var url = $(this).attr('url');
			if(text == '' || text=='文明上网，理性发言...')
			{
				showErrorMsg('评论内容不能为空！' , '消息提示'); 
				return false;
			}
			else
			{
				if(mb_strlen(text) > 1000){
					showErrorMsg('评论内容不能超过500个汉字' , '消息提示'); 
					return false;
				}
			}
		    $.ajax({
		        type: "post",
			    url: url ,
			    data: {'bid': bid , 'to' : toid ,'text': text},
				dataType: 'json',
			    success: function(data){
				    if(data.code == 1)
					{
						var tpl   = '<div class="Blog_right1_8">';
							tpl  +=   '<div class="Blog_right_img1"><a href="' +data.info.url+ '" >' + data.info.header + '</a></div>';
							tpl  +=	  '<div class="Blog_right_font1">';
							tpl  +=       '<p class="Blog_p5"><span><a href="' +data.info.url+ '" >' + data.info.username + '</a></span>' + data.info.dateline + '</p>';
							tpl  +=       '<p class="Blog_p6">' + data.info.content + '</p>';
							tpl  +=		  '<div class="div1"><a href="javascript:void(0);" class="Blog_a10"  toid=' + data.info.fuid + ' bid=' + data.info.bid + ' cid=' + data.info.cid + '>回复</a> | 　<a class="comment_del_mark" style="cursor:pointer" url="' + data.info.delurl + '">删除</a>　| 　<a href="javascript:showJuBao(\'/blog/ViewReport.html\','+data.info.cid+')" class="box_report" cid="' + data.info.cid + '">举报</a></div>';
							tpl  +=		  '<div class="z_move_comment" style="display:none"></div>';
							tpl  +=    '</div><div class="Blog_line1"></div></div>';
							$('.Blog_tit3:first').after(tpl);
							$('#reply').val('文明上网，理性发言...');
					}
					else if(data.code == -1)
					{
						showErrorMsg(data.info , '消息提示'); 
			        }
                },
			    error: function(){//请求出错处理
                        
                }
		    });
			
		});
		//底部评论重置
		$('#reset_comment').click(function(){
			$('#reply').val('文明上网，理性发言...');
		});
		//取消回复
		$('#qx_comment').live('click' , function(){
			$('.z_move_comment').html('').hide();
		});


		$('#rmsg, #reply').live({
		    focus:function(){
			    if($(this).val() == '文明上网，理性发言...'){
			        $(this).val('');
			    }
			},
			blur:function(){
		        if($(this).val() == ''){
			        $(this).val('文明上网，理性发言...');
			    }
			}
		});
		//删除留言确认
		$('.comment_del_mark').live('click' , function(){
			var url = $(this).attr('url');
			asyncbox.confirm('删除留言','确认', function(action){
				if(action == 'ok')
				{
					location.href = url;
				}
			});
		});
		//删除时间确认
		$('.del_article_id').click(function(){
			var delurl = $(this).attr('delurl');
			asyncbox.confirm('删除文章','确认', function(action){
				if(action == 'ok')
				{
					location.href = delurl;
				}
			});
		});
		/*
		//字数限制
		$('#rmsg, #reply').live('keyup', function(){
			var id = $(this).attr('id');
			var left = Util.calWbText($(this).val(), 500);
			var eid = '#errmsg';
			
			if(id == 'reply') eid =  '#rerrmsg';
			if (left >= 0)
		        $(eid).html('您还可以输入<span>' + left + '</span>字');
		    else
		        $(eid).html('<font color="red">您已超出<span>' + Math.abs(left) + '</span>字 </font>');
		});
		*/
		//加载表情
	    $('#face').qqFace({id : 'facebox1', assign : 'reply', path : '/image/qqface/'});
	    $('#mface').qqFace({id : 'facebox', assign : 'rmsg', path:'/image/qqface/'});
	    
		/*
		$('#class_one_id').change(function(){
			alert(123213);
			var id = parseInt($(this).val() , 10);
			if(id == 0) return false;
			$('.hidden_son_class span').each(function( index , dom ){
				if( dom.attr('cid')  == id )
				{
				}
			});
		});
		*/
		//转载文章
		var turn_url = "/blog/viewClassPart.html";
		$('#repost_bar').click(function(){
			if(isOnLine == '' )
			{
				//showErrorMsg('登录之后才能进行此操作' , '消息提示');
				showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');
				return false;
			}
			var id = $(this).attr('bid');
			asyncbox.open({
				id  : 'turn_class_thickbox',
				url : turn_url,
				title : '转载文章',
				width : 330,
				height : 131,
				scroll : 'no',
				data : {
					'id'	 : id
				},
				callback : function(action){
					if(action == 'close'){
						$.cover(false);
					}
				}
			});
		});
		/*
	    //转发文章
	    $('#repost_bar').live('click' , function(){
			if(isOnLine == '' )
			{
				//showErrorMsg('登录之后才能进行此操作' , '消息提示');
				showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');
				return false;
			}
	    	var bid  = $(this).attr('bid');
	    	var url  = $(this).attr('url');
	    	asyncbox.confirm('转载文章','确认', function(action){
	    	  if(action == 'ok'){
	    	    $.ajax({
				type:"POST",
				url:url,	
				data: {
					'bid' : bid 
				},
				dataType: 'json',
				success:function(msg){
				  if(msg.error == 0){
				    showSucceedMsg('转发成功！', '消息提示');
				  }else if(msg.error == 1){
				    //location.href = '/index.php?r=site/login';
					showErrorMsg('操作失败,您需要先登录!', '消息提示', '/site/login.html');
				  }else{
				    showErrorMsg(msg.error_content, '消息提示');
			      }
				}
			  });
	    	  }
	    	});

		});
		*/

	});
</script>
<!--该部分应该放在输出代码块的后面才起作用 -->
<script type="text/javascript">

SyntaxHighlighter.autoloader(
	'applescript			/highlight/scripts/shBrushAppleScript.js',
	'actionscript3 as3		/highlight/scripts/shBrushAS3.js',
	'bash shell				/highlight/scripts/shBrushBash.js',
	'coldfusion cf			/highlight/scripts/shBrushColdFusion.js',
	'cpp c					/highlight/scripts/shBrushCpp.js',
	'c# c-sharp csharp		/highlight/scripts/shBrushCSharp.js',
	'css					/highlight/scripts/shBrushCss.js',
	'delphi pascal			/highlight/scripts/shBrushDelphi.js',
	'diff patch pas			/highlight/scripts/shBrushDiff.js',
	'erl erlang				/highlight/scripts/shBrushErlang.js',
	'groovy					/highlight/scripts/shBrushGroovy.js',
	'java					/highlight/scripts/shBrushJava.js',
	'jfx javafx				/highlight/scripts/shBrushJavaFX.js',
	'js jscript javascript	/highlight/scripts/shBrushJScript.js',
	'perl pl				/highlight/scripts/shBrushPerl.js',
	'php					/highlight/scripts/shBrushPhp.js',
	'text plain				/highlight/scripts/shBrushPlain.js',
	'py python				/highlight/scripts/shBrushPython.js',
	'ruby rails ror rb		/highlight/scripts/shBrushRuby.js',
	'scala					/highlight/scripts/shBrushScala.js',
	'sql					/highlight/scripts/shBrushSql.js',
	'vb vbnet				/highlight/scripts/shBrushVb.js',
	'xml xhtml xslt html	/highlight/scripts/shBrushXml.js'
);
SyntaxHighlighter.all();


function code_hide(id){
	var code = document.getElementById(id).style.display;
	if(code == 'none'){
		document.getElementById(id).style.display = 'block';
	}else{
		document.getElementById(id).style.display = 'none';
	}
}
</script>
  <!-- footer -->
  <div class="Blog_footer" style='clear:both'>
    <div><a href="http://www.chinaunix.net/about/index.shtml" target="_blank" rel="nofollow">关于我们</a> | <a href="http://www.it168.com/bottomfile/it168.shtml" target="_blank" rel="nofollow">关于IT168</a> | <a href="http://www.chinaunix.net/about/connect.html" target="_blank" rel="nofollow">联系方式</a> | <a href="http://www.chinaunix.net/about/service.html" target="_blank" rel="nofollow">广告合作</a> | <a href="http://www.it168.com//bottomfile/flgw/fl.htm" target="_blank" rel="nofollow">法律声明</a> | <a href="http://sso.chinaunix.net/Register?return_url=http%3A%2F%2Fblog.chinaunix.net%2F
" target="_blank" rel="nofollow">免费注册</a>
      <p>Copyright  2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有 </p>
      <div>感谢所有关心和支持过ChinaUnix的朋友们
        <p>京ICP证041476号 京ICP证060528号</p>
      </div>
    </div>
  </div>
</div>
<script language="javascript">

//全局错误提示弹出框
function showErrorMsg(content, title, url){
	var url = url || '';
	var title = title || '消息提示';
	var html = '';
	html += '<div class="HT_layer3_1 HT_layer3_2"><ul><li><p><span class="login_span1"></span>' + content + '</p></li>';
	if(url == '' || url.length == 0){
		html += '<li class="HT_li1"><input type="button" class="HT_btn2"  onclick=\'close_windows("error_msg")\'></li>';	
	} else {
		html += '<li class="HT_li1"><input type="button" class="login_btn1" onclick="location.href=\'' + url + '\'"></li>';
	}
	html += '</ul></div>';
	$.cover(true);
	   asyncbox.open({
		 id: 'error_msg',
		 title : title,
		 html : html,
		 'callback' : function(action){
			 if(action == 'close'){
				 $.cover(false);
			 }
		 }
	});
}

//全局正确提示
function showSucceedMsg(content, title , url ){
	var url = url || '';
	var title = title || '消息提示';
	var html = '';
	html += '<div class="HT_layer3_1 HT_layer3_2"><ul><li><p><span class="login_span2"></span>' + content + '</p></li>';
	if(url == '' || url.length == 0){
		html += '<li class="HT_li1"><input type="button" class="HT_btn2"  onclick=\'close_windows("error_msg")\'></li>';	
	} else {
		html += '<li class="HT_li1"><input type="button" class="HT_btn2" onclick="location.href=\'' + url + '\'"></li>';
	}
	html += '</ul></div>';
	$.cover(true);
	asyncbox.open({
		 id: 'error_msg',
		 title : title,
		 html : html,
		 'callback' : function(action){
			 if(action == 'close'){
				 $.cover(false);
			 }
		 }
	});
}

//关闭指定id的窗口
function close_windows(id){
	$.cover(false);
	$.close(id);
}


//公告
var tID;
var tn;                        // 高度
var nStopTime = 5000;        // 不同行间滚动时间隔的时间，值越小，移动越快
var nSpeed = 50;            // 滚动时，向上移动一像素间隔的时间，值越小，移动越快
var isMove = true;
var nHeight = 25;
var nS = 0;
var nNewsCount = 3;

/**
 * n 用于表示是否为第一次运行
 **/
function moveT(n)
{
    clearTimeout(tID)
    var noticev2 = document.getElementById("noticev2")
    nS = nSpeed;
    
    // 只在第一次调用时运行，初始化环境（有没有参数）
    if (n)
    {
        // 设置行高
        noticev2.style.lineHeight = nHeight + "px";
        // 初始化显示位置
        tn = 0;
        // 刚进入时在第一行停止时间
        nS = nStopTime;
    }
    
    // 判断鼠标是否指向层
    if (isMove)
    {
        // 向上移动一像素
        tn--;
        // 如果移动到最下面一行了，则移到顶行
        if (Math.abs(tn) == nNewsCount * nHeight)
        {
            tn = 0;
        }
        // 设置位置
        noticev2.style.marginTop = tn + "px";
        // 完整显示一行时，停止一段时间
        if (tn % nHeight == 0)
        {
            nS = nStopTime;
        }
    }

    tID = setTimeout("moveT()", nS);
}
moveT(1);    // 此处可以传入任何参数
</script>
<script language="javascript" src="http://stat.it168.com/pv.js"></script>
<script>
function sendPV(){
    var pvTrack = new PvTrack();
    pvTrack.type = 35; // 频道类别ID
    pvTrack.channel = 189; // 频道ID
    pvTrack.pageType = 0;
    pvTrack.track();
}
window.setTimeout("sendPV()", 1000);
</script>
<script type="text/javascript">
  var _gaq = _gaq || [];
  _gaq.push(['_setAccount', 'UA-20237423-2']);
  _gaq.push(['_setDomainName', '.chinaunix.net']);
  _gaq.push(['_trackPageview']);

  (function() {
    var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
    ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
    var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
  })();

</script>
<script type="text/javascript">
var _bdhmProtocol = (("https:" == document.location.protocol) ? " https://" : " http://");
document.write(unescape("%3Cscript src='" + _bdhmProtocol + "hm.baidu.com/h.js%3F0ee5e8cdc4d43389b3d1bfd76e83216b' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript" src="/js/jquery.qqFace.js"></script>
</body>
</html>
